package xyz.scootaloo.oj.offer;

import org.junit.Test;

/**
 * @author flutterdash@qq.com
 * @since 2021/4/13 15:38
 */
public class P36 {

    public Node treeToDoublyList(Node root) {
        if (root == null)
            return null;
        Node pointer = dfs(root);
        Node tail = gotoEnd(pointer);
        Node head = gotoHead(pointer);
        bind(tail, head);

        return head;
    }

    private Node dfs(Node current) {
        if (current.left == null && current.right == null)
            return current;

        Node leftNode;
        if (current.left != null) {
            leftNode = gotoEnd(dfs(current.left)); // 获取右节点
            bind(leftNode, current);
        }

        Node rightNode;
        if (current.right != null) {
             rightNode = gotoHead(dfs(current.right)); // 获取左节点
             bind(current, rightNode);
        } else {
            return current;
        }

        return current;
    }

    private Node gotoEnd(Node node) {
        Node pointer = node;
        while (pointer.right != null)
            pointer = pointer.right;
        return pointer;
    }

    private Node gotoHead(Node node) {
        Node pointer = node;
        while (pointer.left != null)
            pointer = pointer.left;
        return pointer;
    }

    private void bind(Node pre, Node next) {
        pre.right = next;
        next.left = pre;
    }

    static class Node {
        public int val;
        public Node left;
        public Node right;

        public Node() {}

        public Node(int _val) {
            val = _val;
        }

        public Node(int _val,Node _left,Node _right) {
            val = _val;
            left = _left;
            right = _right;
        }
    }

    @Test
    public void test0() {
        Node node1 = new Node(1);
        Node node2 = new Node(2);
        Node node3 = new Node(3);
        Node node4 = new Node(4);
        Node node5 = new Node(5);

        node4.left = node2;
        node4.right = node5;

        node2.left = node1;
        node2.right = node3;

        Node head = treeToDoublyList(node4);
        System.out.println(head);
    }

    @Test
    public void test1() {
        Node node1 = new Node(1);
        Node node1_ = new Node(-1);
        Node node9 = new Node(9);

        node1.right = node1_;
        node1_.right = node9;

        Node head = treeToDoublyList(node1);
        System.out.println(head);
    }

    @Test
    public void test2() {
        Node node30 = new Node(30);
        Node node13 = new Node(13);
        Node node28 = new Node(28);
        Node node44_ = new Node(-44);
        Node node35_ = new Node(-35);

        node30.left = node13;
        node13.left = node28;
        node28.left = node44_;
        node44_.right = node35_;

        Node head = treeToDoublyList(node30);
        System.out.println(head);
    }

    @Test
    public void test3() {
        Node node27 = new Node(27);
        Node node99_ = new Node(-99);
        Node node34_ = new Node(-34);
        Node node8_ = new Node(-8);
        Node node8 = new Node(8);
        Node node55 = new Node(55);
        Node node58 = new Node(58);
        Node node59 = new Node(59);
        Node node68 = new Node(68);

        node27.left = node99_;
        node27.right = node55;

        node99_.right = node34_;
        node34_.right = node8_;
        node8_.right = node8;

        node55.right = node58;
        node58.right = node59;
        node59.right = node68;

        // [-99,-34,-8,8,27,55,58,59,68]
        Node head = treeToDoublyList(node27);
        System.out.println(head);
    }

}
